Биномиальный коэффициент

Биномиальный коэффициент — коэффициент перед членом разложения бинома Ньютона [math]\displaystyle{ (1+x)^n }[/math] по степеням [math]\displaystyle{ x }[/math]. Коэффициент при [math]\displaystyle{ x^k }[/math] обозначается [math]\displaystyle{ \textstyle\binom{n}{k} }[/math] или [math]\displaystyle{ \textstyle C_n^k }[/math] и читается «биномиальный коэффициент из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math]» (или «число сочетаний из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math]»):

[math]\displaystyle{ (1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\ldots+\binom{n}{n}x^n =\sum_{k=0}^{n} \binom{n}{k} x^k }[/math]

для натуральных степеней [math]\displaystyle{ n }[/math].

Биномиальные коэффициенты могут быть также определены для произвольных действительных показателей [math]\displaystyle{ n }[/math]. В случае произвольного действительного числа [math]\displaystyle{ n }[/math] биномиальные коэффициенты определяются как коэффициенты разложения выражения [math]\displaystyle{ (1+x)^n }[/math] в бесконечный степенной ряд:

[math]\displaystyle{ (1+x)^n=\sum_{k=0}^{\infty} \binom{n}{k} x^k }[/math],

где в случае неотрицательных целых [math]\displaystyle{ n }[/math] все коэффициенты [math]\displaystyle{ \textstyle\binom{n}{k} }[/math] при [math]\displaystyle{ k\gt n }[/math] обращаются в нуль и поэтому данное разложение является конечной суммой.

В комбинаторике биномиальный коэффициент [math]\displaystyle{ \textstyle\binom{n}{k} }[/math] для неотрицательных целых чисел [math]\displaystyle{ n }[/math] и [math]\displaystyle{ k }[/math] интерпретируется как количество сочетаний из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math], то есть как количество всех (нестрогих) подмножеств (выборок) размера [math]\displaystyle{ k }[/math] в [math]\displaystyle{ n }[/math]-элементном множестве.

Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.

Явные формулы

Вычисляя коэффициенты в разложении [math]\displaystyle{ (1+x)^n }[/math] в степенной ряд, можно получить явные формулы для биномиальных коэффициентов [math]\displaystyle{ \textstyle\binom{n}{k} }[/math].

Для всех действительных чисел [math]\displaystyle{ n }[/math] и целых чисел [math]\displaystyle{ k }[/math]:

[math]\displaystyle{ \binom{n}{k}=\begin{cases} \frac{n(n-1)(n-2)\cdot\ldots\cdot(n-k+1)}{k!}, & k\geqslant 0\\ 0, & k\lt 0 \end{cases} }[/math],

где [math]\displaystyle{ k! }[/math] обозначает факториал числа [math]\displaystyle{ k }[/math].

Для неотрицательных целых [math]\displaystyle{ n }[/math] и [math]\displaystyle{ k }[/math] также справедливы формулы:

[math]\displaystyle{ \binom{n}{k} = \begin{cases} \frac{n!}{k!(n-k)!}, & 0\leqslant k\leqslant n\\ 0, & k\gt n \end{cases} }[/math].

Для целых отрицательных показателей коэффициенты разложения бинома [math]\displaystyle{ (1+x)^{-n} }[/math] равны:

[math]\displaystyle{ \binom{-n}{k} = \begin{cases} (-1)^k\cdot\frac{(n+k-1)!}{k!(n-1)!}, & k\geqslant 0\\ 0, & k\lt 0 \end{cases} }[/math].

Треугольник Паскаля

Тождество:

[math]\displaystyle{ {n\choose k}={n-1\choose k-1}+{n-1\choose k} }[/math]

позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел [math]\displaystyle{ n }[/math], [math]\displaystyle{ k }[/math] в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:

[math]\displaystyle{ \begin{matrix} n=0: & & & & & 1 & & & &\\ n=1: & & & & 1 & & 1 & & &\\ n=2: & & & 1 & & 2 & & 1 & &\\ n=3: & & 1 & & 3 & & 3 & & 1 &\\ n=4: & 1 & & 4 & & 6 & & 4 & & 1\\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots & \end{matrix} }[/math].

Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от той, что выписана здесь, поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, Омару Хайяму).

Если в каждой строке треугольника Паскаля все числа разделить на [math]\displaystyle{ 2^n }[/math] (это сумма всех чисел в строке), то все строки при стремлении [math]\displaystyle{ n }[/math] к бесконечности примут вид функции нормального распределения.

Свойства

Производящие функции

Для фиксированного значения [math]\displaystyle{ n }[/math] производящей функцией последовательности биномиальных коэффициентов [math]\displaystyle{ \tbinom{n}{0},\;\tbinom{n}{1},\;\tbinom{n}{2}, \dots }[/math] является:

[math]\displaystyle{ \sum_{k=0}^{\infty} \binom{n}{k} x^k = (1+x)^n }[/math].

Для фиксированного значения [math]\displaystyle{ k }[/math] производящая функция последовательности коэффициентов [math]\displaystyle{ \tbinom{0}{k},\;\tbinom{1}{k},\;\tbinom{2}{k}, \dots }[/math] равна:

[math]\displaystyle{ \sum_n \binom{n}{k} y^n = \frac{y^k}{(1-y)^{k+1}} }[/math].

Двумерной производящей функцией биномиальных коэффициентов [math]\displaystyle{ \tbinom{n}{k} }[/math] для целых [math]\displaystyle{ n,k }[/math] является:

[math]\displaystyle{ \sum_{n,k} \binom{n}{k} x^k y^n = \frac{1}{1-y-xy} }[/math], или [math]\displaystyle{ \sum_{n=0}^\infty\sum_{k=0}^n \binom{n}{k} x^k y^n = \frac{1}{1-y-xy} }[/math].

Делимость

Из теоремы Люка следует, что:

коэффициент [math]\displaystyle{ \textstyle \binom{n}{k} }[/math] нечётен [math]\displaystyle{ \iff }[/math] в двоичной записи числа [math]\displaystyle{ k }[/math] единицы не стоят в тех разрядах, где в числе [math]\displaystyle{ n }[/math] стоят нули;
коэффициент [math]\displaystyle{ \textstyle \binom{n}{k} }[/math] некратен простому числу [math]\displaystyle{ p }[/math] [math]\displaystyle{ \iff }[/math] в [math]\displaystyle{ p }[/math]-ичной записи числа [math]\displaystyle{ k }[/math] все разряды не превосходят соответствующих разрядов числа [math]\displaystyle{ n }[/math];
в последовательности биномиальных коэффициентов [math]\displaystyle{ \textstyle \binom{n}{0},\;\binom{n}{1},\;\ldots,\;\binom{n}{n} }[/math]:
- все числа не кратны заданному простому [math]\displaystyle{ p }[/math] [math]\displaystyle{ \iff }[/math] число [math]\displaystyle{ n }[/math] представимо в виде [math]\displaystyle{ mp^k-1 }[/math], где натуральное число [math]\displaystyle{ m\lt p }[/math];
- все числа, кроме первого и последнего, кратны заданному простому [math]\displaystyle{ p }[/math] [math]\displaystyle{ \iff }[/math] [math]\displaystyle{ n=p^k }[/math];
- количество нечётных чисел равно степени двойки, показатель которой равен количеству единиц в двоичной записи числа [math]\displaystyle{ n }[/math];
- чётных и нечётных чисел не может быть поровну;
- количество чисел, не кратных простому [math]\displaystyle{ p }[/math], равно [math]\displaystyle{ (a_1+1)\cdots(a_m+1) }[/math], где числа [math]\displaystyle{ a_1,\;\ldots,a_m }[/math] — разряды [math]\displaystyle{ p }[/math]-ичной записи числа [math]\displaystyle{ n }[/math]; а число [math]\displaystyle{ \textstyle m=\lfloor\log_p{n}\rfloor + 1 }[/math], где [math]\displaystyle{ \lfloor\cdot\rfloor }[/math] — функция «пол», — это длина данной записи.

Основные тождества

[math]\displaystyle{ {n\choose k}={n-1\choose k-1}+{n-1\choose k} }[/math].
[math]\displaystyle{ \binom{n}{k}=(-1)^k\binom{-n+k-1}{k} }[/math].
[math]\displaystyle{ {n\choose k}={n\choose n-k} }[/math] (правило симметрии).
[math]\displaystyle{ {n\choose k}=\frac{n}{k}{n - 1\choose k-1} }[/math] (вынесение за скобки).
[math]\displaystyle{ {n\choose{\color{Green}m}}{{\color{Green}m}\choose n-{\color{Green}k}}={n\choose{\color{Green}k}}{{\color{Green}k}\choose n-{\color{Green}m}} }[/math] (замена индексов).
[math]\displaystyle{ (n-k){n\choose k}=n{n-1\choose k} }[/math].

Бином Ньютона и следствия

[math]\displaystyle{ {n\choose 0}+{n\choose 1}+\ldots+{n\choose n}=2^n }[/math], где [math]\displaystyle{ n\in\mathbb{N} }[/math].
[math]\displaystyle{ \sum_{i+j=m}\binom{n}{j}\binom{n}{i}(-1)^j= \begin{cases} \binom{n}{m/2}, & \text{если} \ m\equiv 0\pmod{2},\\ 0, & \text{если}\ m\equiv 1\pmod{2}. \end{cases} }[/math]
[math]\displaystyle{ \sum_{j=k}^{n} \binom{n}{j} (-1)^j = (-1)^k \binom{n-1}{k-1} }[/math].
[math]\displaystyle{ {n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0 }[/math], где [math]\displaystyle{ n\in\mathbb{N} }[/math].
Более сильное тождество: [math]\displaystyle{ {n\choose 0}+{n\choose 2}+\ldots+{n\choose 2\lfloor n/2\rfloor}=2^{n-1} }[/math], где [math]\displaystyle{ n\in\mathbb{N} }[/math].
[math]\displaystyle{ \sum_{k=-a}^{a}(-1)^{k}{2a\choose k+a}^3 =\frac{(3a)!}{(a!)^3} }[/math],

а более общем виде

[math]\displaystyle{ \sum_{k=-a}^a(-1)^k{a+b\choose a+k} {b+c\choose b+k}{c+a\choose c+k} = \frac{(a+b+c)!}{a!\,b!\,c!} }[/math].

Свёртка Вандермонда и следствия

Свёртка Вандермонда:

[math]\displaystyle{ \sum_{k}{r\choose m+k}{s\choose n-k}={r+s\choose m+n} }[/math],

где [math]\displaystyle{ m, n\in\mathbb{Z}, }[/math] а [math]\displaystyle{ r, s \in\mathbb{R} }[/math]. Это тождество получается вычислением коэффициента при [math]\displaystyle{ x^{m+n} }[/math] в разложении [math]\displaystyle{ (1+x)^{r} (1+x)^{s} }[/math] с учётом тождества [math]\displaystyle{ (1+x)^{r+s}=(1+x)^r(1+x)^s }[/math]. Сумма берётся по всем целым [math]\displaystyle{ k }[/math], для которых [math]\displaystyle{ \textstyle{r\choose m+k}{s\choose n-k}\ne0 }[/math]. Для произвольных действительных [math]\displaystyle{ r }[/math], [math]\displaystyle{ s }[/math] число ненулевых слагаемых в сумме будет конечно.

Следствие свёртки Вандермонда:

[math]\displaystyle{ {n\choose 0}{a\choose a}-{n\choose 1}{a+1\choose a}+\ldots+(-1)^n{n\choose n}{a+n\choose a}=(-1)^n{a\choose n} }[/math].

Более общее тождество:

[math]\displaystyle{ \sum_{i=0}^{p} (-1)^i{p\choose i}\prod_{m=1}^{n} {i+s_m\choose s_m} =0 }[/math], если [math]\displaystyle{ \sum_{m=1}^n{s_m} \lt p }[/math].

Ещё одним следствием свёртки является следующее тождество: [math]\displaystyle{ {n\choose 0}^2+{n\choose 1}^2+\ldots+{n\choose n}^2={2n\choose n} }[/math].

Другие тождества

[math]\displaystyle{ \frac{4}{n} \sum_{k=1}^{n}k^2\binom{2n}{n+k}=2^{2n} }[/math], где [math]\displaystyle{ n }[/math] — натуральное число.
[math]\displaystyle{ \sum_{k=1}^n \frac{(-1)^{k-1}}{k}{n \choose k}=\sum_{k=1}^n \frac{1}{k} = H_n }[/math] — [math]\displaystyle{ n }[/math]-е гармоническое число.
Мультисекция ряда [math]\displaystyle{ (1+x)^n }[/math] даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом [math]\displaystyle{ s }[/math] и смещением [math]\displaystyle{ t }[/math] [math]\displaystyle{ (0\leqslant t\lt s) }[/math] в виде конечной суммы из [math]\displaystyle{ s }[/math] слагаемых:

[math]\displaystyle{ \binom{n}{t}+\binom{n}{t+s}+\binom{n}{t+2s}+\ldots=\frac{1}{s}\sum_{j=0}^{s-1}\left(2\cos\frac{\pi j}{s}\right)^n\cos\frac{\pi(n-2t)j}{s} }[/math].

Также имеют место равенства:

[math]\displaystyle{ \begin{alignat}{2} \binom{n}{3}&=\frac{n(n-1)(n-2)}{\color{Green}2}-\sum_{i=2}^{n-1}{(n-i)(n-i+1)}= \\ &=n(n-1)(n-2)-\sum_{i=2}^{n-1}{(n-i)({\color{Green}2}n-i+1)}= \\ &=3\binom{n}{3}-2\binom{n}{3}; \\ \end{alignat} }[/math]

[math]\displaystyle{ \begin{alignat}{2} \binom{n}{4}&=\frac{n(n-1)(n-2)(n-3)}{\color{Green}2}-\sum_{i=3}^{n-1}{(n-i)\left(n(n-1)-\sum_{i_0=1}^{i-2}i_0\right)}= \\ &=n(n-1)(n-2)(n-3)-\sum_{i=3}^{n-1}{(n-i)\left({\color{Green}2}n(n-1)-\sum_{i_0=1}^{i-2}i_0\right)}= \\ &=24\binom{n}{4}-23\binom{n}{4}; \\ \end{alignat} }[/math]

[math]\displaystyle{ \begin{alignat}{2} \binom{n}{5}&=\frac{n(n-1)(n-2)(n-3)(n-4)}{\color{Green}2}- \\ &-\sum_{i=4}^{n-1}{(n-i)\left(n(n-1)(n-2)-\sum_{i_0=1}^{i-3}\sum_{i_1=1}^{i_0}i_1\right)}= \\ &=n(n-1)(n-2)(n-3)(n-4)-\\ &-\sum_{i=4}^{n-1}{(n-i)\left({\color{Green}2}n(n-1)(n-2)-\sum_{i_0=1}^{i-3}\sum_{i_1=1}^{i_0}i_1\right)}= \\ &=120\binom{n}{5}-119\binom{n}{5}.\end{alignat} }[/math]

Откуда следует:

[math]\displaystyle{ \binom{n}{3}=\frac{\sum\limits_{i=2}^{n-1}{(n-i)(2n-i+1)}}{2}=\frac{\sum\limits_{i=2}^{n-1}{(n-i)\left(2A_n^1-\binom{i-1}{1}\right)}}{2}; }[/math]

[math]\displaystyle{ \binom{n}{4}=\frac{\sum\limits_{i=3}^{n-1}{(n-i)\left(2n(n-1)-\sum\limits_{i_0=1}^{i-2}i_0\right)}}{23}=\frac{\sum\limits_{i=3}^{n-1}{(n-i)\left(2A_n^2-\binom{i-1}{2}\right)}}{23}; }[/math]

[math]\displaystyle{ \begin{alignat}{2} &\binom{n}{5}=\frac{\sum\limits_{i=4}^{n-1}{(n-i)\left(2n(n-1)(n-2)-\sum\limits_{i_0=1}^{i-3}\sum\limits_{i_1=1}^{i_0}i_1\right)}}{119}= \\ &=\frac{\sum\limits_{i=4}^{n-1}{(n-i)\left(2A_n^3-\binom{i-1}{3}\right)}}{119}; \\ \end{alignat} }[/math]

[math]\displaystyle{ \binom{n}{k}=\frac{\sum\limits_{i=k-1}^{n-1}{(n-i)\left(2A_n^{k-2}-\binom{i-1}{k-2}\right)}}{k!-1} }[/math],

где [math]\displaystyle{ A_n^k }[/math] — количество размещений из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k }[/math].

Матричные соотношения

Если взять квадратную матрицу, отсчитав [math]\displaystyle{ N }[/math] элементов по катетам треугольника Паскаля и повернув матрицу на любой из четырёх углов, то детерминант этих четырёх матриц равен ±1 при любом [math]\displaystyle{ N }[/math], причём детерминант матрицы с вершиной треугольника в верхнем левом углу равен 1.

В матрице [math]\displaystyle{ \begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix} }[/math] числа на диагонали [math]\displaystyle{ i+j=\mathrm{Const} }[/math] повторяют числа строк треугольника Паскаля ([math]\displaystyle{ i, j = 0, 1,\dots }[/math]). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием:

[math]\displaystyle{ \begin{bmatrix}\binom{i+j}{i}\end{bmatrix} = UU^T }[/math],

где [math]\displaystyle{ U=\begin{bmatrix}\tbinom{i}{j}\end{bmatrix} }[/math]. Обратная матрица к [math]\displaystyle{ U }[/math] имеет вид:

[math]\displaystyle{ U^{-1}=\begin{bmatrix}(-1)^{i+j}\binom{i}{j}\end{bmatrix} }[/math].

Таким образом, можно разложить обратную матрицу к [math]\displaystyle{ \begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix} }[/math] в произведение двух строго диагональных матриц: первая матрица — верхнетреугольная, а вторая получается из первой путём транспонирования, что позволяет дать явное выражение для обратных элементов:

[math]\displaystyle{ \begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n}=\sum_{k=0}^{p}(-1)^{m+n}\binom{k}{m}\binom{k}{n} }[/math], где [math]\displaystyle{ i }[/math], [math]\displaystyle{ j }[/math], [math]\displaystyle{ m }[/math], [math]\displaystyle{ n = 0 \dots p }[/math].

Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы [math]\displaystyle{ \begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix} }[/math], недостаточно приписать новую строку и столбец. Столбец [math]\displaystyle{ j }[/math] матрицы [math]\displaystyle{ \begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix} }[/math] есть многочлен степени [math]\displaystyle{ j }[/math] по аргументу [math]\displaystyle{ i }[/math], следовательно, первые p столбцов образуют полный базис в пространстве векторов длины [math]\displaystyle{ p }[/math]+1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени [math]\displaystyle{ p-1 }[/math]. Нижняя строка матрицы [math]\displaystyle{ \begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n} }[/math] ортогональна любому такому вектору.

[math]\displaystyle{ \begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{p,n}=\sum_{k=0}^{p}(-1)^{p+n}\binom{k}{p}\binom{k}{n} = (-1)^{p+n}\binom{p}{n} }[/math]

[math]\displaystyle{ \sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{P}_{a}(n) = 0 }[/math] при [math]\displaystyle{ a\lt p }[/math], где [math]\displaystyle{ {P}_{a}(n) }[/math] многочлен степени [math]\displaystyle{ a }[/math].

Если произвольный вектор длины [math]\displaystyle{ p+1 }[/math] можно интерполировать многочленом степени [math]\displaystyle{ i \lt p }[/math], то скалярное произведение со строками [math]\displaystyle{ i+1, i+2, \dots, p }[/math] (нумерация с 0) матрицы [math]\displaystyle{ \begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n} }[/math] равно нулю. Используя тождество выше и равенство единицы скалярного произведения нижней строки матрицы [math]\displaystyle{ \begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n} }[/math] на последний столбец матрицы [math]\displaystyle{ \begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix} }[/math], получаем:

[math]\displaystyle{ \sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{n}^{p} = p! }[/math].

Для показателя большего [math]\displaystyle{ p }[/math] можно задать рекуррентную формулу:

[math]\displaystyle{ \sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{n}^{p+a} = p!{P}_{2a}(p)={f}_{a}(p) }[/math],

где многочлен

[math]\displaystyle{ {P}_{2a+2}(p) = \sum_{x=1}^{p} x{P}_{2a}(x);\quad a\geqslant 0;\quad {P}_{0}(p)=1 }[/math].

Для доказательства сперва устанавливается тождество:

[math]\displaystyle{ {f}_{a}(p+1)=\sum_{x=0}^{a} {(p+1)}^{x+1}{f}_{a-x}(p) }[/math].

Если требуется найти формулу не для всех показателей степени, то:

[math]\displaystyle{ {P}_{2a}(p) = \frac{p}{{2}^{a}}\binom{p+a}{a}{Q}_{a-1}(p);\quad a\gt 0 }[/math].

Старший коэффициент [math]\displaystyle{ {Q}_{a-1}(p) }[/math] равен 1, потребуется a-1 значений, чтобы найти другие коэффициенты:

[math]\displaystyle{ {Q}_{a-1}(p)=p(p+1){T}_{a-3}(p) }[/math] для [math]\displaystyle{ a\equiv 1\pmod{2}; a\geqslant 3 }[/math].

Асимптотика и оценки

[math]\displaystyle{ \binom{2n}{n}\sim\frac{2^{2n}}{\sqrt{\pi n}} }[/math].
[math]\displaystyle{ \sum^{m}_{k=0} \binom{n}{k}\leqslant\frac{n}{(n/2-m)^2}2^{n-3} }[/math] при [math]\displaystyle{ m\lt \frac{n}{2} }[/math] (неравенство Чебышёва).
[math]\displaystyle{ \sum\limits_{k=0}^{m} \binom{n}{k}\leqslant 2^{nH(\frac{m}{n})} }[/math], при [math]\displaystyle{ m \le \frac{n}{2} }[/math] (энтропийная оценка), где [math]\displaystyle{ H(x)=-x\log_2x-(1-x)\log_2(1-x) }[/math] — энтропия.
[math]\displaystyle{ \sum^{n/2-\lambda}_{k=0} \binom{n}{k}\leqslant 2^ne^{-2\lambda^2/n} }[/math] (неравенство Чернова).

Непосредственно из формулы Стирлинга следует, что для [math]\displaystyle{ \alpha \in (0;1) }[/math] верно [math]\displaystyle{ C_n^{\alpha n} \sim \sqrt{\frac{1}{2 \pi \alpha (1-\alpha) n}} \left({\frac{1}{\alpha}}\right)^{\alpha n} \left({\frac{1}{1-\alpha}}\right)^{(1-\alpha)n} = \left({\frac{1}{\alpha^\alpha {(1-\alpha)}^{(1-\alpha)}} + o(1)}\right)^{n} }[/math].

Целозначные полиномы

Биномиальные коэффициенты [math]\displaystyle{ \tbinom{x}{0}=1, \tbinom{x}{1}=x, \tbinom{x}{2}=\tfrac{x^2}{2}-\tfrac{x}{2} }[/math], … являются целозначными полиномами от [math]\displaystyle{ x }[/math], то есть принимают целые значения при целых значениях [math]\displaystyle{ x }[/math], — это нетрудно понять, например, по треугольнику Паскаля. Более того, они образуют базис целозначных полиномов, в котором все целозначные полиномы выражаются как линейные комбинации с целыми коэффициентами.^[1]

В то же время стандартный базис [math]\displaystyle{ 1, x, x^2 }[/math], … не позволяет выразить все целочисленные полиномы, если использовать только целые коэффициенты, так как уже [math]\displaystyle{ \tbinom{x}{2}=\tfrac{x^2}{2}-\tfrac{x}{2} }[/math] имеет дробные коэффициенты при степенях [math]\displaystyle{ x }[/math].

Этот результат обобщается на полиномы многих переменных. А именно, если полином [math]\displaystyle{ R(x_1, \dots, x_m) }[/math] степени [math]\displaystyle{ k }[/math] имеет вещественные коэффициенты и принимает целые значения при целых значениях переменных, то

[math]\displaystyle{ R(x_1, \dots, x_m) = P\left(\binom{x_1}{1}, \dots, \binom{x_1}{k}, \dots, \binom{x_m}{1}, \dots, \binom{x_m}{k}\right) }[/math],

где [math]\displaystyle{ P }[/math] — полином с целыми коэффициентами.^[2]

Алгоритмы вычисления

Биномиальные коэффициенты можно вычислить с помощью рекуррентной формулы [math]\displaystyle{ \tbinom{n}{k}=\tbinom{n-1}{k}+\tbinom{n-1}{k-1} }[/math], если на каждом шаге [math]\displaystyle{ n }[/math] хранить значения [math]\displaystyle{ \tbinom{n}{k} }[/math] при [math]\displaystyle{ k=\overline{0,1,\;\ldots,n} }[/math]. Этот алгоритм особенно эффективен, если нужно получить все значения [math]\displaystyle{ \tbinom{n}{k} }[/math] при фиксированном [math]\displaystyle{ n }[/math]. Алгоритм требует [math]\displaystyle{ O(n) }[/math] памяти ([math]\displaystyle{ O(n^2) }[/math] при вычислении всей таблицы биномиальных коэффициентов) и [math]\displaystyle{ O(n^2) }[/math] времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени), где [math]\displaystyle{ O }[/math] — «[math]\displaystyle{ o }[/math]» большое.

При фиксированном значении [math]\displaystyle{ k }[/math] биномиальные коэффициенты могут быть вычислены по рекуррентной формуле [math]\displaystyle{ \tbinom{n}{k}=\tfrac{n}{n-k}\cdot\tbinom{n-1}{k} }[/math] с начальным значением [math]\displaystyle{ \tbinom{k}{k}=1 }[/math]. Для вычисления значения [math]\displaystyle{ \tbinom{n}{k} }[/math] этот метод требует [math]\displaystyle{ O(1) }[/math] памяти и [math]\displaystyle{ O(n) }[/math] времени.

Если требуется вычислить коэффициенты [math]\displaystyle{ \tbinom{n}{k} }[/math] при фиксированном значении [math]\displaystyle{ n }[/math], можно воспользоваться формулой [math]\displaystyle{ \tbinom{n}{k}=\tfrac{n-k+1}{k}\cdot\tbinom{n}{k-1} }[/math] при начальном условии [math]\displaystyle{ \tbinom{n}{0}=1 }[/math]. При каждом шаге итерации числитель уменьшается на [math]\displaystyle{ 1 }[/math] (начальное значение равно [math]\displaystyle{ n }[/math]), а знаменатель соответственно увеличивается на [math]\displaystyle{ 1 }[/math] (начальное значение — [math]\displaystyle{ 1 }[/math]). Для вычисления значения [math]\displaystyle{ \tbinom{n}{k} }[/math] этот метод требует [math]\displaystyle{ O(1) }[/math] памяти и [math]\displaystyle{ O(k) }[/math] времени.

Примечания

↑ Прасолов В. В. Глава 12. Целозначные многочлены // Многочлены. — М.: МЦНМО, 1999, 2001, 2003.
↑ Ю. Матиясевич. Десятая проблема Гильберта. — Наука, 1993.

Литература

Биномиальные коэффициенты // Энциклопедический словарь Брокгауза и Ефрона : в 86 т. (82 т. и 4 доп.). — СПб., 1890—1907.
Фукс Д., Фукс М. Арифметика биномиальных коэффициентов // Квант. — 1970. — № 6. — С. 17—25.
Кузьмин О. В. Треугольник и пирамида Паскаля: свойства и обобщения // Соросовский Образовательный Журнал. — 2000. — Т. 6, № 5. — С. 101—109.
Ландо С. К. Теневое исчисление // VIII летняя школа «Современная математика». — Дубна, 2008.
Винберг Э. Б. Удивительные арифметические свойства биномиальных коэффициентов // Математическое просвещение. — 2008. — Вып. 12. — С. 33–42.
Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Математические основы информатики = Concrete Mathematics. A Foundation for Computer Science. — 2-е. — М.: Мир; Бином. Лаборатория знаний; «Вильямс», 1998—2009. — 703, 784 с. — ISBN 95-94774-560-7, 78-5-8459-1588-7.

[1] Прасолов В. В. Глава 12. Целозначные многочлены // Многочлены. — М.: МЦНМО, 1999, 2001, 2003.

[2] Ю. Матиясевич. Десятая проблема Гильберта. — Наука, 1993.

[1]

[2]